package com.dycong.common.leetcode;

import java.util.Arrays;

/**
 * 目标和
 *
 * 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
 *
 * 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
 *
 * 示例 1:
 *
 * 输入: nums: [1, 1, 1, 1, 1], S: 3
 * 输出: 5
 * 解释:
 *
 * -1+1+1+1+1 = 3
 * +1-1+1+1+1 = 3
 * +1+1-1+1+1 = 3
 * +1+1+1-1+1 = 3
 * +1+1+1+1-1 = 3
 *
 * 一共有5种方法让最终目标和为3。
 * 注意:
 *
 * 数组非空，且长度不会超过20。
 * 初始的数组的和不会超过1000。
 * 保证返回的最终结果能被32位整数存下。
 * @author dycong
 * @date 2019/12/6 8:28
 */
public class FindTargetSumWays_494 {


    public static void main(String[] args) {
        FindTargetSumWays_494 findTargetSumWays_494 = new FindTargetSumWays_494();
//        int[] nums = {1, 1, 1, 1, 1};
        int[] nums = {1000};
        int S = 3;
/*        System.out.println("S: " + S + "  " + findTargetSumWays_494.findTargetSumWays(nums, S));
        System.out.println("S: " + 0 + "  " + findTargetSumWays_494.findTargetSumWays2(nums, 1));
        System.out.println("S: " + S + "  " + findTargetSumWays_494.findTargetSumWays2(nums, S));*/
        System.out.println("S: " + 0 + "  " + findTargetSumWays_494.findTargetSumWays3(nums, -1000));
//        System.out.println("S: " + S + "  " + findTargetSumWays_494.findTargetSumWays3(nums, S));
    }

    int count = 0;

    /**
     * 方法一：枚举
     * 我们可以使用递归，枚举出所有可能的情况。具体地，当我们处理到第 i 个数时，我们可以将它添加 + 或 -，递归地搜索这两种情况。
     * 当我们处理完所有的 N 个数时，我们计算出所有数的和，并判断是否等于 S。
     * <p>
     * 时间复杂度：O(2^N)O(2N)，其中 NN 是数组 nums 的长度。
     * <p>
     * 空间复杂度：O(N)O(N)，为递归使用的栈空间大小。
     *
     * @param nums
     * @param S
     * @return
     */
    public int findTargetSumWays(int[] nums, int S) {
        exhaustivity(nums, 0, 0, S);
        return count;
    }

    public void exhaustivity(int[] nums, int i, int sum, int S) {
        if (i == nums.length) {
            if (sum == S) {
                count++;
            }
        } else {
            exhaustivity(nums, i + 1, sum + nums[i], S);
            exhaustivity(nums, i + 1, sum - nums[i], S);
        }
    }

    /**
     * 方法二：动态规划
     * 这道题也是一个常见的背包问题，我们可以用类似求解背包问题的方法来求出可能的方法数。
     * <p>
     * 我们用 dp[i][j] 表示用数组中的前 i 个元素，组成和为 j 的方案数。考虑第 i 个数 nums[i]，它可以被添加 + 或 -，因此状态转移方程如下：
     * <p>
     * dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]
     * 也可以写成递推的形式：
     * <p>
     * dp[i][j + nums[i]] += dp[i - 1][j]
     * dp[i][j - nums[i]] += dp[i - 1][j]
     * 由于数组中所有数的和不超过 1000，那么 j 的最小值可以达到 -1000。在很多语言中，是不允许数组的下标为负数的，因此我们需要给 dp[i][j] 的第二维预先增加 1000，即：
     * <p>
     * dp[i][j + nums[i] + 1000] += dp[i - 1][j + 1000]
     * dp[i][j - nums[i] + 1000] += dp[i - 1][j + 1000]
     * <p>
     * 复杂度分析
     * <p>
     * 时间复杂度：O(N*\text{sum})O(N∗sum)，其中 NN 是数组 nums 的长度。
     * <p>
     * 空间复杂度：O(N*\text{sum})O(N∗sum)。
     *
     * @param nums
     * @param S
     * @return
     */
    public int findTargetSumWays2(int[] nums, int S) {
        int[][] dp = new int[nums.length][2001];
        dp[0][nums[0] + 1000] = 1;
        dp[0][-nums[0] + 1000] += 1;

        for (int i = 1; i < nums.length; i++) {
            for (int sum = -1000; sum <= 1000; sum++) {
                if (dp[i - 1][sum + 1000] > 0) {
                    dp[i][sum + nums[i] + 1000] += dp[i - 1][sum + 1000];
                    dp[i][sum - nums[i] + 1000] += dp[i - 1][sum + 1000];
                }
            }
        }
        print(dp);
        return S > 1000 ? 0 : dp[nums.length - 1][S + 1000];
    }

    /**
     * 方法三：动态规划 + 空间优化
     * 我们发现，方法二中动态规划的状态转移方程中，dp[i][...] 只和 dp[i - 1][...] 有关，因此我们可以优化动态规划的空间复杂度，只需要使用两个一维数组即可。
     * <p>
     * 复杂度分析
     * 时间复杂度：O(N*\text{sum})O(N∗sum)，其中 NN 是数组 nums 的长度。
     * 空间复杂度：O(\text{sum})O(sum)。
     *
     * @param nums
     * @param S
     * @return
     */
    public int findTargetSumWays3(int[] nums, int S) {
        int[] dp = new int[2001];
        dp[nums[0] + 1000] = 1;
        dp[-nums[0] + 1000] += 1;

        for (int i = 1; i < nums.length; i++) {
            int[] next = new int[2001];
            for (int sum = -1000; sum <= 1000; sum++) {
                if (dp[sum + 1000] > 0) {
                    next[sum + nums[i] + 1000] += dp[sum + 1000];
                    next[sum - nums[i] + 1000] += dp[sum + 1000];
                }
            }
            dp = next;
        }
        System.out.println(Arrays.toString(dp));
        return S > 1000 ? 0 : dp[S + 1000];
    }

    private void print(int[][] nums) {
        for (int[] ints : nums) {
            System.out.println(Arrays.toString(ints));
        }
    }


}
